package com.xxd.algo.newcode.base01.class05;

import java.util.LinkedList;
import java.util.Stack;


public class Code04_IsBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        public boolean isBST;
        public int min;
        public int max;

        public Info(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public static Info process(Node head) {
        if (head == null) {
            return null;
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        int min = head.value;
        int max = head.value;

        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }

        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }

        boolean isBST = false;

        boolean left = leftInfo == null || (leftInfo.isBST && leftInfo.max < head.value);
        boolean rigth = rightInfo == null || (rightInfo.isBST && rightInfo.min > head.value);

        isBST = left && rigth;
        return new Info(isBST, min, max);
    }

    public static boolean isBST1(Node head) {
        if (head == null) {
            return true;
        }

        Info info = process(head);
        return info.isBST;
    }

    public static void process(Node node, LinkedList<Node> inOrderList) {
        if (node == null) {
            return;
        }
        process(node.left, inOrderList);
        inOrderList.add(node);
        process(node.right, inOrderList);
    }

    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> inOrderList = new LinkedList<>();
        process(head, inOrderList);
        int pre = Integer.MIN_VALUE;
        for (Node cur : inOrderList) {
            if (pre >= cur.value) {
                return false;
            }
            pre = cur.value;
        }
        return true;
    }

    public static boolean inOrderUnRecur(Node head) {
        if (head == null) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (head.value <= pre) {
                    return false;
                }
                pre = head.value;
                head = head.right;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Node head = new Node(6);
        head.left = new Node(5);
        head.right = new Node(7);
        head.left.left = new Node(2);
        //  head.left.right = new Node(5);
        //  head.right.left = new Node(6);
        head.right.right = new Node(8);

        System.out.println(isBST(head));
        System.out.println(isBST1(head));
    }
}
